package org.nowcoder.leetcode.BTree;

/**
 * Title  : 106. Construct Binary Tree from Inorder and Postorder Traversal
 * Source : https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 * Author : XrazYang
 * Date   : 2023-09-12
 */

public class LeetCode_106 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int len = inorder.length;
        TreeNode root = buildTree2(inorder, 0, len - 1, postorder, 0, len - 1);
        return root;
    }

    /**
     * 递归三部曲：
     * 1. 递归的返回值和参数
     * 2. 递归终止条件
     * 3. 梳理单层递归逻辑
     */
    private TreeNode buildTree2(int[] inorder, int iLeft, int iRight, int[] postorder, int pLeft, int pRight) {
        //切割中序：在中序遍历中找到后序遍历的最后结点
        int index = -1;
        for (int i = iLeft; i <= iRight; i++) {
            if (inorder[i] == postorder[pRight]) {
                index = i;
                break;
            }
        }
        if (index != -1) {
            TreeNode node = new TreeNode(inorder[index]);
            //对于左子树
            node.left = buildTree2(inorder, iLeft, index - 1, postorder, pLeft, pLeft + index - iLeft - 1);
            //对于右子树
            node.right = buildTree2(inorder, index + 1, iRight, postorder, pRight - (iRight - index), pRight - 1);
            return node;
        }
        return null;
    }
}
